Prim-algoritmus

A Prim-algoritmus egy összefüggő súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. Működési elve, hogy csúcsonként haladva építi fel a fát, egy tetszőleges csúcsból kiindulva és minden egyes lépésben a lehető legolcsóbb élt keresi meg egy következő csúcshoz. Az algoritmust először Vojtěch Jarník írta le 1930-ban, de ez az eredmény ismeretlen maradt. Tőle függetlenül Robert C. Prim 1957-ben és Edsger Dijkstra 1959-ben újra felfedezték. Ezért az algoritmust nevezik még DJP-algoritmusnak, Jarník-algoritmusnak vagy Prim−Jarník-algoritmusnak is.

További ehhez hasonló algoritmus még a Kruskal-algoritmus és a Boruzvka-algoritmus. Ezek az algoritmusok megkeresik egy feltehetőleg nem összefüggő gráf minimális feszítő erdejét. Ezzel szemben a Prim-algoritmus egyszerű verziója egy összefüggő gráfban találja meg a minimális feszítőfát. Azonban a Prim-algoritmus alkalmazása a gráf különböző kapcsolódási pontjain szintén megtalálja a minimális feszítőerdőt. Ami a bonyolultságot illeti, mindhárom algoritmus egyformán gyors sűrű gráfokban, de lassabb más kifinomultabb algoritmusoknál. Az elég sűrű gráfok esetén a Prim-algoritmus lineáris idő alatt lefuttatható, azonosan vagy túlteljesítve más algoritmusok időbeli megkötéseit.